package class5;

import common.TreeNode;
import common.TreeNodeUtils;

/**
 * 二叉树的最大深度
 * 给定一个二叉树 root ，返回其最大深度。
 * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
 */
public class Code04_TreeHeigh {
    public static void main(String[] args) {
        TreeNode treeNode1 = TreeNodeUtils.getTreeNode();
        int i = maxDepth(treeNode1);
        System.out.println("i = " + i);
    }

    public static int maxDepth(TreeNode root) {
        // 基础条件：如果当前节点为空，返回高度0
        if (root == null) {
            return 0;
        }

        // 递归计算左子树和右子树的高度
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);

        // 返回较大的子树高度 + 1（当前节点的高度）
        return Math.max(leftHeight, rightHeight) + 1;
        //因为当前节点的高度要加上 1，表示当前节点自身的贡献。如果当前节点有左右子树，那么它的高度就是左右子树高度的最大值加上 1（即包含当前节点的高度）。
        //这是因为二叉树的深度或高度定义为从根节点到最远叶子节点的路径长度，而当前节点作为路径的一部分，必须加上。
    }
}
